package org.example.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。
 * 不考虑答案输出的顺序。
 */
public class Code438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int n = p.length();
        int[] pStr = new int[26];
        int[] sStr = new int[26];
        for (int i = 0; i < n; i++) {
            pStr[p.charAt(i) - 97]++;
        }

        for (int left = 0, right = 0; right < s.length(); ) {
            char c = s.charAt(right);
            sStr[c - 97]++;
            if (right - left + 1 == n) {
                if (isSame(pStr, sStr)) {
                    result.add(left);
                }
                sStr[s.charAt(left) - 97]--;
                left++;
                right++;
            } else {
                right++;
            }
        }
        return result;
    }

    private boolean isSame(int[] pStr, int[] sStr) {
        for (int i = 0; i < 26; i++) {
            if (pStr[i] != sStr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Code438 solution = new Code438();

        // 测试用例1
        String s1 = "cbaebabacd";
        String p1 = "abc";
        System.out.println("输入: s = \"" + s1 + "\", p = \"" + p1 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s1, p1));
        // 预期输出: [0, 6]

        // 测试用例2
        String s2 = "abab";
        String p2 = "ab";
        System.out.println("\n输入: s = \"" + s2 + "\", p = \"" + p2 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s2, p2));
        // 预期输出: [0, 1, 2]

        // 测试用例3
        String s3 = "baa";
        String p3 = "aa";
        System.out.println("\n输入: s = \"" + s3 + "\", p = \"" + p3 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s3, p3));
        // 预期输出: [1]

        // 边界测试用例
        String s4 = "a";
        String p4 = "aa";
        System.out.println("\n输入: s = \"" + s4 + "\", p = \"" + p4 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s4, p4));
        // 预期输出: []
    }
}
